package com.singzi.algorithm;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int []arr = {1,3,4,6,733,6,7,2,5,6,1,8,9,4,6,6,77,5,5,5,5,5,543,52,5,25,25,2,52,5,25,2,52,5,25,2,52,53,253};
        Sort sort = new Sort();
        sort.quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
class Sort{

    public void quickSort(int[]arr){
        int n = arr.length;
        qSort(arr, 0, n-1);

    }
    public void qSort(int []arr, int start, int end){
        int pivot = arr[start];
//        System.out.println(Arrays.toString(arr));
        int i = start, j = end;
        while (i < j){
            while (i < j && arr[j] > pivot) j--;
            while (i < j && arr[i] < pivot) i++;
            if(arr[i] == arr[j] && i < j){
                i++;
            }
            else{
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }


        }
        if (i-1>start) qSort(arr,start,i-1);
        if (j+1<end) qSort(arr,j+1,end);
    }
}